//
//  YKSort.c
//  data01
//
//  Created by gaofeng on 2021/3/27.
//

#include "YKSort.h"
void InsertSortHalf(int a[],int n){
    printf("InsertSortHalf\n");
    int i,j,l,m,h,t;
    for (i=1; i<n; i++) {
        t = a[i];
        l=0;
        h=i-1;
        while (l<=h) {
            m = (l+h)/2;
            if (a[m]>t) {
                h=m-1;
            } else {
                l=m+1;
            }
        }
        for (j=i-1; j>=h+1; j--) {
            a[j+1]=a[j];
        }
        a[h+1]=t;
    }
    
}
void InsertSortA(int a[],int n){
    printf("InsertSort_A\n");
    int i,j,temp;
    for (i=1; i<n; i++) {
        temp = a[i];
        for (j=i-1; temp<a[j]; j--) {
            a[j+1]=a[j];
        }
        a[j+1] = temp;
    }
}

void InsertSort(int a[],int n){
    printf("InsertSort\n");
    int i,j;
    for (i = 2; i<n; i++) {
        a[0] = a[i];
        for (j=i-1; a[0]<a[j]; j--) {
            a[j+1]=a[j];
        }
        a[j+1]=a[0];
    }
}
void ShellSort(int a[],int n){
    printf("ShellSort\n");
    int t; // 临时变量，用于临时存储
    for (int dk=n/2; dk>=1; dk=dk/2) { // 步长设置
        for (int i=dk+1; i<n; ++i) {
            if (a[i]<a[i-dk]) { // 相邻步长间距数据比较
                t=a[i];
                int j=i-dk;
                for (; j>=0&&t<a[j]; j-=dk) {
                    a[j+dk]=a[j];
                }
                a[j+dk]=t;
            }
        }
    }
}
void BubbleSort(int a[],int n){
    int flag  ;
    for (int i =0; i<n; i++) {
        flag = 0;
        for (int j=n-1; j>i; j--) {
            if (a[j-1]>a[j]) {
                int t = a[j];
                a[j] = a[j-1];
                a[j-1] = t;
                flag = 1;
            }
        }
        if (flag==0) {
            return;
        }
    }
}

void QuickSort(int a[],int b,int e){
    if (b<e) {
        int key = a[b];
        int i = b;
        int j = e;
        while (i<j) {
            while (i<j && a[j] > key) {
                --j;
            }
            if (i<j) {
                a[i]=a[j];
                ++i;
            }
            while (i<j && a[i] <key) {
                i++;
            }
            if (i<j) {
                a[j]=a[i];
                j--;
            }
        }
        a[i]=key;
        QuickSort(a, b, i-1);
        QuickSort(a, i+1, e);
    }
}
void SelectSort(int a[],int n){
    printf("SelectSort\n");
    int min ;
    for (int i=0; i<n-1; i++) {
        min = i;
        for (int j=i+1; j<n; j++) {
            if (a[j]<a[min]) {
                min = j;
            }
        }
        if (min != i) {
            int t = a[min];
            a[min] = a[i];
            a[i] = t;
        }
    }
}
void AdjustDown(int a[],int k, int len){
    a[0] = a[k];
    for (int i= 2*k; i<=len; i*=2) {
        if (i<len && a[i]<a[i+1]) {
            i++;
        }
        if (a[0]>=a[i]) {
            break;
        }else{
            a[k] =a[i];
            k=i;
        }
    }
    a[k] = a[0];
}
void BuildMaxHeap(int a[],int len){
    for (int i = len/2; i>0; i--) {
        AdjustDown(a, i, len);
    }
}
void HeapSort(int a[],int n){
    BuildMaxHeap(a, n);
    for (int i=n; i>1; i--) {
        int t = a[i];
        a[i] = a[1];
        a[1] = t;
        AdjustDown(a, 1, i-1);
    }
}

